The present invention relates generally to computer applications with high-performance graphics capabilities, and to subassemblies and methods for use in such applications.
Many software applications include built-in xe2x80x9crenderingxe2x80x9d or xe2x80x9cdrawingxe2x80x9d programs to build images of graphics primitives, such as lines, circles, etc., for display. The graphics primitives are laid out or rendered in a buffer memory prior to being displayed. Building an image by such rendering programs may occur by allocating a partition in the main memory address space as the buffer for rendering a graphic image. Data between the main memory and the buffer is exchanged as required by the demands of rendering. The buffer may be an on-screen video memory that displays the graphic while it is being built, an off-screen video memory partition or imaging area that will be swapped into the on-screen video memory partition when it is time to display the graphic primitive, or an address space serving as either an on-screen memory or an off-screen memory. An off-screen memory imaging area is a partition of memory that is capable of rendering graphics primitives without displaying them on a viewable device; it is an area of memory that can be addressed as if it were a graphics device.
A particular interest to the present application is the rendering of lines. Straight, solid lines may be rendered through the so-called xe2x80x9cbrute-force approachxe2x80x9d or the xe2x80x9cprimitive line-drawing method,xe2x80x9d of which Bresenham""s algorithm is an example. The brute-force approach is a straightforward way to compute a pixel-by-pixel representation of a straight line that first requires that the equation of a line, y=mx+b, be solved and applied pixel-by-pixel. This approach, while simple, is computationally intensive and requires the use of real-number arithmetic for each pixel thus computed. Bresenham""s algorithm is the usual technique for drawing a straight, solid line. Integer arithmetic is used to quickly calculate the individual pixels to be turned on. By carrying an error term, the average slope of the line is followed exactly, without having to perform multiplication at each pixel.
While the rendering of straight, solid lines is well established in the art, the drawing of patterned or stippled lines is of more concern. Certain computer software applications do not support the representation or drawing of stippled or patterned lines, so that patterned lines cannot be easily viewed through a standard viewing mechanism such as a monitor or other on-screen viewing device. Sun Microsystem""s Java 1.1, a programming language used by many applications, for instance, does not support the drawing of patterned lines. There is no mechanism currently available through the Java 1.1 language interface that is capable of rendering patterned lines. Patterned or stippled lines as used herein refer to non-solid lines in which some type of pattern, such as dots, dashes, etc., is apparent. The term xe2x80x9cpatternxe2x80x9d generally refers to an array containing run-length encoding made up of xe2x80x9conxe2x80x9d and xe2x80x9coffxe2x80x9d segments; the term xe2x80x9cpattern repeat lengthxe2x80x9d refers to the sum of the pattern""s segment lengths. Thus a pattern of {3, 2, 1, 2}, has four pattern segments: a first, xe2x80x9conxe2x80x9d segment with a length of three pixels, a second, xe2x80x9coffxe2x80x9d segment with a length of two pixels, a third, xe2x80x9conxe2x80x9d segment with a length of one pixel, and a fourth, xe2x80x9coffxe2x80x9d segment with a length of two pixels. The pattern repeat length of this pattern is the sum of the segment lengths, or 8 pixels. A pattern is typically drawn over and over until the entire length of the patterned line is exhausted. An empty pattern ({ }) is equivalent to a single xe2x80x9conxe2x80x9d segment of infinite length.
A patterned line is typically represented by rendering the segments of the line. The so-called xe2x80x9cline-segmentxe2x80x9d solution calculates the extents of each line segment of a patterned line using the original endpoints of the line and employs a substantial amount of floating-point calculations to determine segment endpoints of the line. While workable, the line-segment solution results in an inaccurate representation of the line due to round-off error typically introduced during the floating-point calculations. Pixels drawn using the line-segment approach are not guaranteed to fall on the original primitive rendering of a line; the question becomes how to treat pixels that do not fall squarely on the line. This problem is not encountered when patterned lines are drawn according to the Bresenham line draw algorithm in which the particular pixels or dots between the two endpoints that will be drawn is determined. While solid lines with their integer coordinates are readily rendered in this manner, the primitive line-drawing method of the Bresenham algorithm cannot be easily used to render the fractional coordinates commonly associated with the segments of a patterned line.
Consider, for example, that a line from Cartesian coordinates [0, 0] to [9, 3] is to be rendered. [0, 0] refers to the beginning endpoint of the line, generally the leftmost endpoint. [9, 3] refers to the ending endpoint, generally the rightmost endpoint of the line. Diagram 1 illustrates the results of applying a typical line-drawing primitive to render a Cartesian coordinate representation of this line in a graphical display area, with each xe2x80x9c#xe2x80x9d representing a pixel that is rendered as xe2x80x9con.xe2x80x9d
Now suppose that a pattern which has an initial segment of length 5 is to be imposed on the line. The coordinates of the endpoint of the initial segment would be, in real number coordinates, [4.74,1.58]. The endpoints, however, must be specified in integer coordinates. There are two methods available for converting real numbers into integer values-ignoring the fractional components (xe2x80x9ctruncationxe2x80x9d) or picking the xe2x80x9cnearestxe2x80x9d integer value (xe2x80x9croundingxe2x80x9d). For example, if one were to convert the real numbers to integers by ignoring the fractional components, the endpoint for the end of the initial segment would be chosen as [4,1]. Diagram 2 depicts a typical rendering of the line segment from [0,0] to [4,1]: 
This method correctly chooses pixels that originally appeared on the line. However, the pixel [4,1] is turned xe2x80x9conxe2x80x9d even though it only partially lies within the 5-unit pattern segment; adherence to the specified pattern is not maintained.
An alternate approach to coordinate conversion is to round up or round down a real number depending upon the value of the fractional remainder of the number, as measured in tenths. Thus, a number having a fractional remainder of greater than 0.5 would be rounded up to the next integer number while a number having a fractional remainder of equal to or less than 0.5 would be rounded down. If this standard rounding technique were applied in the example, the resulting endpoint would be [5,2]. Diagram 3 depicts a typical rendering of the line segment from [0,0] to [5,2]: 
Notice that applying this technique caused the pixels at [4,2] and [5,2] to be turned on. Neither of these pixels were in the original line rendering, so some coherence with the original line rendering has been lost.
From an efficiency standpoint, the line-segment solution is very costly in that it calls the primitive line-drawing method for each segment of a patterned line. Since a pattern can have segments as small as one pixel, such calls of the primitive line-drawing method can fail to render certain portions of a line if the calculations end up with identical endpoints (beginning and ending) due to mathematical round-off. This results from the fact that the implementation of some primitive line-drawing methods render zero-length lines as a single pixel, others do not render them at all. This possibility is illustrated by the following example in which a line is drawn from [0,0] to [5,5] with an initial pattern segment of length 1. The endpoint of the first segment would be (in real number coordinates) [0.707,0.707]. If integer conversion is the technique applied to derive the endpoint, the result is [0,0], the same as the beginning point of the line. Standard rounding techniques may avoid this situation, although may have other deficiencies as previously described.
Therefore, according to the present invention, a method of rendering patterned lines in a processing environment that supports the rendering of graphical primitives in an off-screen imaging area is disclosed. An off-screen imaging area, such as a partition of a memory of the processing environment that is capable of rendering graphics primitives without displaying them on a viewable device, is created. The off-screen imaging area is representative of an on-screen graphics area of a viewable device having a plurality of pixels and is empty when initially created. The size of the off-screen imaging area in the memory is defined by a bounding rectangle of the patterned line to be rendered. The off-screen imaging area is next filled with a suitable, distinct background color that is representative of pixels being xe2x80x9coff.xe2x80x9d A solid line is then rendered within the off-screen imaging area from beginning endpoint to ending endpoint of the patterned line to be drawn by changing the color of the pixels that fall on the line from the background color to another line color. A pattern, having contiguous on- and off-segments and a repeat length, is next applied to the solid line by means of a filtering mechanism whereby pixels that correspond to off-segments of the pattern are filtered out. The resulting patterned line is transferred from the off-screen imaging area to a viewable device wherein it can be rendered on the on-screen graphics area of the viewable device and thus viewed. The above is performed for each patterned line to be rendered. The methodology of the present invention may be implemented by a computer program of a computer-readable medium.
The filtering that occurs when the pattern is applied to the solid line is practiced for each of the pixels. The color of the pixel must be determined. If the pixel is the line color and thus xe2x80x9con,xe2x80x9d the distance of the pixel from the beginning endpoint of the solid line is calculated. A remainder distance of the quotient obtained by dividing the distance of the pixel from the beginning endpoint by the pattern repeat length of the pattern is next calculated. If the remainder distance falls entirely within an on-segment, the line color of the pixel is maintained as the line color. If, however, the remainder distance falls entirely within an off-segment of the pattern, the pixel is turned xe2x80x9coffxe2x80x9d by changing its color from the line color to the background color. If the remainder distance does not fall entirely within an on-segment or an off-segment, this is indicative of the pixel spanning two contiguous segments of the pattern, an on-segment and an off-segment. In this event, anti-aliasing may be used in the filtering procedure. If anti-aliasing is to be used, the intensity of the pixel is set by applying anti-aliasing to the pixel in accordance with the percentage of the pixel that falls within each of the contiguous on- and off-segments. If anti-aliasing is not to be used, the pixel is turned off if it is found to lie predominately within the off-segment of the contiguous segments of the pattern.